package cn.com.algorithm.sort;

import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;

/**
 * 快速排序-改进
 * 1. 切换到插入排序
 * - 对于小数组， 快速排序比插入排序慢
 * - 因为递归， 快速排序的sortO方法在小数组中也会调用自己
 * ---> 在排序小数组时应该切换到插入排序
 * if(hi <= lo) return; ----> if(hi <= lo + M) { Insertion.sort(&, lo, hi); return; }
 *
 * 2. 三取样切分
 * - 子数组的一小部分元素的中位数来切分数组
 * - 将数组切分为三部分， 分别对应小于、 等于和大于切分元素的数组元素
 */

public class Quick3way {

    public static void sort(Comparable[] a) {
        StdRandom.shuffle(a); //打乱数组a,消除对输入的依赖
        sort(a, 0, a.length-1);
    }

    private static void sort(Comparable[] a, int lo, int hi)
    {   //调用此方法的公有方法sort()请见算法2.5
        if (hi <= lo) return;
        int lt = lo, i = lo+1, gt = hi;
        Comparable v = a[lo];
        while (i <= gt)
        {
            int cmp = a[i].compareTo(v);
            if (cmp < 0)
                exch(a, lt++, i++);
            else if (cmp > 0)
                exch(a, i, gt--);
            else i++;
        }
        sort(a, lo, lt - 1);
        sort(a, gt + 1, hi);
    }

    private static int partition(Comparable[] a, int lo, int hi) {
        int i = lo, j = hi+1;
        Comparable v = a[lo];
        while(true) {
            while(less(a[++i], v))
                if(i == hi)
                    break;
            while(less(v, a[--j]))
                if(j == lo)
                    break;
            if(i >= j)
                break;
            exch(a, i, j);
        }
        exch(a, lo, j);
        return j;
    }

    /**
     * 比较元素
     * @param v
     * @param w
     * @return
     */
    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }

    /**
     * 将元素交换位置
     * @param a
     * @param i
     * @param j
     */
    private static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    private static void show(Comparable[] a) { // 在单行中打印数组
        for (int i = 0; i < a.length; i++)
            StdOut.print(a[i] + " ");
        StdOut.println();
    }

    public static boolean isSorted(Comparable[] a) { // 测试数组元素是否有序
        for (int i = 1; i < a.length; i++)
            if (less(a[i], a[i - 1])) return false;
        return true;
    }

    public static void main(String[] args) {
        Integer[] a = {1,3,4,2,9,6,5,8,7,10};
        sort(a);
        assert isSorted(a);
        show(a);
    }
}
